package com.study.sort;

import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

// 归并排序
public class MergeSort
{
    int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};

    int[] assist = new int[arr.length];

    // // 2020版数据结构与算法
    @Test
    void sort()
    {
        sort(arr, 0, arr.length - 1);

    }

    void sort(int[] arr, int low, int high)
    {
        if (low >= high) return;

        int mid = low + (high - low) / 2;

        sort(arr, low, mid);
        sort(arr, mid + 1, high);

        merge(arr, low, mid, high);
    }

    // 合并数组以 mid 为分界的左右两个有序区间
    void merge(int[] arr, int low, int mid, int high)
    {
        int p1 = low, p2 = mid + 1, i = low;

        while (p1 <= mid && p2 <= high) {
            if (less(arr[p1], arr[p2])) {
                assist[i++] = arr[p1++];
            } else {
                assist[i++] = arr[p2++];
            }
        }
        while (p1 <= mid) {
            assist[i++] = arr[p1++];
        }
        while (p2 <= high) {
            assist[i++] = arr[p2++];
        }
        System.arraycopy(assist, low, arr, low, high - low + 1);
    }

    public static boolean less(int v, int w)
    {
        return v - w < 0;
    }

    @BeforeEach
    void printArrBefore()
    {
        System.out.println(Arrays.toString(arr));
    }

    @AfterEach
    void printArrAfter()
    {
        System.out.println(Arrays.toString(arr));
    }
}
